package NO7_Hash;


import java.util.HashMap;
import java.util.Map;

/**
 * 2025-08-14
 * 力扣 - 219. 存在重复元素 II
 * <p>
 * 给你一个整数数组 nums 和一个整数 k ，
 * 判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。
 * 如果存在，返回 true ；否则，返回 false 。
 */
public class ContainsNearbyDuplicateMain {
    public static void main(String[] args) {
        System.out.println(containsNearbyDuplicate(new int[]{1, 2, 3, 1, 2, 3}, 2));
    }

    // time_out
//    public static boolean containsNearbyDuplicate(int[] nums, int k) {
//        if (nums.length == 0 || k < 0) {
//            return false;
//        }
//
//        for (int i = 0; i < nums.length; i++) {
//            for (int j = i + 1; j < nums.length; j++) {
//                if (nums[i] == nums[j] && Math.abs(j - i) <= k) {
//                    return true;
//                }
//            }
//        }
//
//        return false;
//    }

    // 使用 HashMap 存储数组元素和对应索引
    public static boolean containsNearbyDuplicate(int[] nums, int k) {
        if (nums.length == 0 || k < 0) {
            return false;
        }

        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i]) && Math.abs(i - map.get(nums[i])) <= k){
                return true;
            }
            map.put(nums[i], i);
        }

        return false;
    }
}
